public class test {
    public class FibonacciSequence {
        // 递归实现（简洁但效率低）
        public static long fibonacciRecursive(int n) {
            if (n <= 1) {
                return n;
            }
            return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
        }

        // 迭代实现（高效，推荐）
        public static long fibonacciIterative(int n) {
            if (n <= 1) {
                return n;
            }
            long a = 0, b = 1;
            for (int i = 2; i <= n; i++) {
                long temp = a + b;
                a = b;
                b = temp;
            }
            return b;
        }

        // 使用矩阵快速幂实现（时间复杂度O(log n)）
        public static long fibonacciMatrix(int n) {
            if (n <= 1) {
                return n;
            }
            long[][] F = {{1, 1}, {1, 0}};
            power(F, n - 1);
            return F[0][0];
        }

        private static void multiply(long[][] F, long[][] M) {
            long x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
            long y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
            long z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
            long w = F[1][0] * M[0][1] + F[1][1] * M[1][1];

            F[0][0] = x;
            F[0][1] = y;
            F[1][0] = z;
            F[1][1] = w;
        }

        private static void power(long[][] F, int n) {
            long[][] M = {{1, 1}, {1, 0}};
            for (int i = 2; i <= n; i++) {
                multiply(F, M);
            }
        }

        public static void main(String[] args) {
            int n = 10; // 计算第10个斐波那契数

            System.out.println("递归方法结果：" + fibonacciRecursive(n));
            System.out.println("迭代方法结果：" + fibonacciIterative(n));
            System.out.println("矩阵快速幂方法结果：" + fibonacciMatrix(n));
        }
    }
}
